package leetcode.p1011;

/**
 * @author: trtan
 * @create: 2021-04-26 08:46
 * @description:
 **/
public class CapacityToShip {
    public int shipWithinDays(int[] weights, int D) {
        int l = 0, r = weights.length * 500, result = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid, weights, D)) {
                result = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return result;
    }

    boolean check(int x, int[] weights, int D) {
        int nowCap = 0;
        int count = 1;
        for (int i = 0; i < weights.length; i++) {
            if (nowCap + weights[i] <= x) {
                nowCap += weights[i];
            } else {
                if (nowCap == 0 || weights[i] > x) {
                    return false;
                }
                nowCap = weights[i];
                count++;
            }
        }
        return count <= D ? true : false;
    }
}
